#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    // void recursion(TreeNode *root, vector<string> &res, string &s)
    // {
    //     if (root->left == nullptr && root->right == nullptr)
    //     {
    //         s += to_string(root->val);
    //         res.push_back(s);
    //         return;
    //     }
    //     s += to_string(root->val) + "->";
    //     string copy_s = s;
    //     if (root->left)
    //     {
    //         recursion(root->left, res, s);
    //         s = copy_s;
    //     }
    //     if (root->right)
    //     {
    //         recursion(root->right, res, s);
    //         s = copy_s;
    //     }
    // }

    // vector<string> binaryTreePaths(TreeNode *root)
    // {
    //     vector<string> res;
    //     string s;
    //     if (root == nullptr)
    //     {
    //         return res;
    //     }
    //     recursion(root, res, s);
    //     return res;
    // }

    // void recursion(TreeNode *root, vector<string> &res, string s)
    // {
    //     s+=to_string(root->val);
    //     if(root->left==nullptr && root->right==nullptr)
    //     {
    //         res.push_back(s);
    //         return;
    //     }
    //     if(root->left)
    //     {
    //         recursion(root->left,res,s+"->");
    //     }
    //     if(root->right)
    //     {
    //         recursion(root->right,res,s+"->");
    //     }
    // }

    // vector<string> binaryTreePaths(TreeNode *root)
    // {
    //     vector<string> res;
    //     if (root == nullptr)
    //     {
    //         return res;
    //     }
    //     string s;
    //     recursion(root, res, s);
    //     return res;
    // }

    vector<string> binaryTreePaths(TreeNode *root)
    {
        stack<TreeNode*> stk;
        stack<string> stk_str;
        vector<string> res;
        if(root==nullptr)
        {
            return res;
        }
        stk.push(root);
        stk_str.push(to_string(root->val));
        while(!stk.empty())
        {
            TreeNode* cur=stk.top();
            stk.pop();
            string s=stk_str.top();
            stk_str.pop();
            if(cur->left==nullptr&&cur->right==nullptr)
            {
                res.push_back(s);
            }
            if(cur->right)
            {
                stk.push(cur->right);
                stk_str.push(s+"->"+to_string(cur->right->val));
            }
            if(cur->left)
            {
                stk.push(cur->left);
                stk_str.push(s+"->"+to_string(cur->left->val));
            }
        }
        return res;
    }
};

int main()
{
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    Solution sol;
    vector<string> str = sol.binaryTreePaths(root);
    for (auto s : str)
    {
        cout << s << endl;
    }
    return 0;
}